/*
提交链接：https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/
1011. 在 D 天内送达包裹的能力
赖德檀 2024/9/17
*/

class Solution {
public:
bool test(vector<int>& weights,int days,int mx)
{
    int num=1,sum=0;
    for(int i=0;i<weights.size();i++)
    {
        if(sum+weights[i]>mx)
        {
            sum=0;
            num++;
        }
        sum+=weights[i];
    }
    return num>days;
}

    int shipWithinDays(vector<int>& weights, int days) {
        int l=ranges::max(weights); //最大重量为左边界
        int r=accumulate(weights.begin(),weights.end(),0);
        //总和为右边界
        int ans=0;
        while(l<=r)
        {
            int mid=(r+l)/2;
            if(test(weights,days,mid))
            {
                l=mid+1;
            }
            else
               {
                r=mid-1;
                ans=mid;
               }
        }
        return ans;
    }
};